package com.demo.java.OD1_50.OD11;

import java.util.Arrays;
import java.util.Scanner;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 快递运输问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/145503052
 */
public class OdMain {

    /**
     * 计算最少需要多少个包裹才能达到目标重量
     * @param arr 包裹重量数组
     * @param weight 目标总重量
     * @return 最少需要的包裹数量
     */
    public static int delivery(int[] arr, int weight) {
        // 对包裹重量数组进行排序，升序排序
        Arrays.sort(arr);

        // 计算包裹的总重量
        int sum = Arrays.stream(arr).sum();

        // 用于累积已选择包裹的重量
        int allSum = 0;

        // 从包裹数组的最后开始，逐个选择包裹
        for (int i = arr.length - 1; i >= 0; --i) {
            // 如果剩余包裹的重量不足以满足目标重量
            if (sum - allSum < weight) {
                // 返回已选包裹的数量（即当前索引及其之后的包裹数量）
                return i + 1;
            } else {
                // 累加当前包裹的重量
                allSum += arr[i];
            }
        }

        // 如果所有包裹都不能满足目标重量，则返回 0
        return 0;
    }

    public static void main(String[] args) {
        try {
            // 创建 Scanner 对象，用于从控制台读取输入
            Scanner s = new Scanner(System.in);

            // 读取包裹重量数组（用逗号分隔）
            String[] lines = s.nextLine().split(",");  // 输入示例："2,5,10,11"

            // 读取目标重量
            int weight = Integer.parseInt(s.nextLine());  // 输入目标重量，例如 20

            // 将字符串数组转换为整数数组
            int[] arr = new int[lines.length];
            for (int i = 0; i < lines.length; i++) {
                arr[i] = Integer.parseInt(lines[i]);  // 将每个包裹的重量转换为整数
            }

            // 调用 delivery 方法，输出最少需要的包裹数量
            System.out.println(delivery(arr, weight));
        } catch (Exception e) {
            // 捕获任何异常，并打印异常信息
            e.printStackTrace();
        }
    }
}
